{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Rectangles Containing Each Point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countRectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计包含每个点的矩形数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>rectangles</code>&nbsp;，其中&nbsp;<code>rectangles[i] = [l<sub>i</sub>, h<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个矩形长为&nbsp;<code>l<sub>i</sub></code>&nbsp;高为&nbsp;<code>h<sub>i</sub></code>&nbsp;。给你一个二维整数数组&nbsp;<code>points</code>&nbsp;，其中&nbsp;<code>points[j] = [x<sub>j</sub>, y<sub>j</sub>]</code>&nbsp;是坐标为&nbsp;<code>(x<sub>j</sub>, y<sub>j</sub>)</code>&nbsp;的一个点。</p>\n",
    "\n",
    "<p>第&nbsp;<code>i</code>&nbsp;个矩形的 <strong>左下角</strong>&nbsp;在&nbsp;<code>(0, 0)</code>&nbsp;处，<strong>右上角</strong>&nbsp;在&nbsp;<code>(l<sub>i</sub>, h<sub>i</sub>)</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个整数数组<em>&nbsp;</em><code>count</code>&nbsp;，长度为&nbsp;<code>points.length</code>，其中<em>&nbsp;</em><code>count[j]</code>是 <strong>包含</strong> 第<em>&nbsp;</em><code>j</code>&nbsp;个点的矩形数目。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>0 &lt;= x<sub>j</sub> &lt;= l<sub>i</sub></code> 且&nbsp;<code>0 &lt;= y<sub>j</sub> &lt;= h<sub>i</sub></code>&nbsp;，那么我们说第&nbsp;<code>i</code>&nbsp;个矩形包含第&nbsp;<code>j</code>&nbsp;个点。如果一个点刚好在矩形的 <strong>边上</strong>&nbsp;，这个点也被视为被矩形包含。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/example1.png\" style=\"width: 300px; height: 509px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]\n",
    "<b>输出：</b>[2,1]\n",
    "<b>解释：</b>\n",
    "第一个矩形不包含任何点。\n",
    "第二个矩形只包含一个点 (2, 1) 。\n",
    "第三个矩形包含点 (2, 1) 和 (1, 4) 。\n",
    "包含点 (2, 1) 的矩形数目为 2 。\n",
    "包含点 (1, 4) 的矩形数目为 1 。\n",
    "所以，我们返回 [2, 1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/example2.png\" style=\"width: 300px; height: 312px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]\n",
    "<b>输出：</b>[1,3]\n",
    "<strong>解释：\n",
    "</strong>第一个矩形只包含点 (1, 1) 。\n",
    "第二个矩形只包含点 (1, 1) 。\n",
    "第三个矩形包含点 (1, 3) 和 (1, 1) 。\n",
    "包含点 (1, 3) 的矩形数目为 1 。\n",
    "包含点 (1, 1) 的矩形数目为 3 。\n",
    "所以，我们返回 [1, 3] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rectangles.length, points.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>rectangles[i].length == points[j].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= l<sub>i</sub>, x<sub>j</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= h<sub>i</sub>, y<sub>j</sub> &lt;= 100</code></li>\n",
    "\t<li>所有&nbsp;<code>rectangles</code>&nbsp;<strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li>所有&nbsp;<code>points</code> <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-rectangles-containing-each-point](https://leetcode.cn/problems/count-number-of-rectangles-containing-each-point/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-rectangles-containing-each-point](https://leetcode.cn/problems/count-number-of-rectangles-containing-each-point/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[2,5]]\\n[[2,1],[1,4]]', '[[1,1],[2,2],[3,3]]\\n[[1,3],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        rectangles.sort(key=lambda x: (x[1], x[0]))\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        \n",
    "        for x, y in rectangles:\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = [0] * len(points)\n",
    "        a = list(g)\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            start = bisect.bisect_left(a, y)\n",
    "            for j in range(start, len(a)):\n",
    "                cands = g[a[j]]\n",
    "                ans[i] += len(cands) - bisect.bisect_left(cands, x)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for r in rectangles:\n",
    "            w = r[0]\n",
    "            h = r[1]\n",
    "\n",
    "            d[h].append(w)\n",
    "        \n",
    "        for h in d:\n",
    "            d[h].sort()\n",
    "        \n",
    "        for p in points:\n",
    "            t = 0\n",
    "            \n",
    "            for h in d:\n",
    "                if p[1] > h:\n",
    "                    continue\n",
    "                t += len(d[h]) - bisect_left(d[h], p[0])\n",
    "            \n",
    "            res.append(t)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        row = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            row[y].append(x)\n",
    "        for l in row.values():\n",
    "            l.sort()\n",
    "        ans = []\n",
    "        for x, y in points:\n",
    "            res = 0\n",
    "            for k, l in row.items():\n",
    "                if k >= y:\n",
    "                    p = bisect_left(l, x)\n",
    "                    res += (len(l) - p)\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        mx_y = max(y for _, y in rectangles)\n",
    "        xs = [[] for _ in range(mx_y + 1)]\n",
    "        for x, y in rectangles:\n",
    "            xs[y].append(x) \n",
    "        for x in xs: x.sort()\n",
    "        ans = [0] * len(points)\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            cnt = 0\n",
    "            for x in xs[py:]:\n",
    "                j = bisect_left(x, px)\n",
    "                cnt += len(x) - j\n",
    "            ans[i] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        arr=[[] for _ in range(102)]\n",
    "        ans=[]\n",
    "        for x,y in rectangles:\n",
    "            arr[y].append(x)\n",
    "        for li in arr:\n",
    "            li.sort()\n",
    "        for x,y in points:\n",
    "            res=0\n",
    "            new=arr[y:]\n",
    "            for cur in new:\n",
    "                idx=bisect_left(cur,x)\n",
    "                res+=len(cur)-idx\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            h[y].append(x)\n",
    "        for x in h.values():\n",
    "            x.sort()\n",
    "        ans = []\n",
    "        for x, y in points:\n",
    "            s = 0\n",
    "            for j in h:\n",
    "                if j >= y:\n",
    "                    s += len(h[j]) - bisect_left(h[j], x)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        arr=[[] for _ in range(102)]\n",
    "        ans=[]\n",
    "        for x,y in rectangles:\n",
    "            arr[y].append(x)\n",
    "        for li in arr:\n",
    "            li.sort()\n",
    "        for x,y in points:\n",
    "            res=0\n",
    "            new=arr[y:]\n",
    "            for cur in new:\n",
    "                idx=bisect_left(cur,x)\n",
    "                res+=len(cur)-idx\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            h[y].append(x)\n",
    "        for x in h.values():\n",
    "            x.sort()\n",
    "        ans = []\n",
    "        hh = sorted(h.keys())\n",
    "        # print(f'hh:{hh}')\n",
    "        for x, y in points:\n",
    "            s = 0\n",
    "            y1 = bisect_left(hh, y)\n",
    "            # print(f'y1:{y1},')\n",
    "            for j in range(y1, len(hh)):\n",
    "                k = hh[j]\n",
    "                s += len(h[k]) - bisect_left(h[k], x)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        max_y = max(y for _, y in rectangles)\n",
    "        xs = [[] for _ in range(max_y + 1)]\n",
    "        for x, y in rectangles:\n",
    "            xs[y].append(x)\n",
    "        for x in xs:\n",
    "            x.sort()\n",
    "        return [sum(len(x) - bisect_left(x, px) for x in xs[py:]) for px, py in points]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort()\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        for l, h in rectangles:\n",
    "            dic[h].append(l)\n",
    "        \n",
    "        ans = []\n",
    "        for x, y in points:\n",
    "            res = 0\n",
    "            for h in range(y, 101):\n",
    "                if not dic[h]:\n",
    "                    continue\n",
    "                idx = bisect_left(dic[h], x)\n",
    "                res += len(dic[h]) - idx\n",
    "            ans.append(res)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        max_y = max(y for _, y in rectangles)\n",
    "        xs = [[] for _ in range(max_y + 1)]\n",
    "        for x, y in rectangles:\n",
    "            xs[y].append(x)\n",
    "        for x in xs:\n",
    "            x.sort()\n",
    "        return [sum(len(x) - bisect_left(x, px) for x in xs[py:]) for px, py in points]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        max_y = max(y for _, y in rectangles)\n",
    "        xs = [[] for _ in range(max_y + 1)]\n",
    "        for x, y in rectangles:\n",
    "            xs[y].append(x)\n",
    "        for x in xs:\n",
    "            x.sort()\n",
    "        return [sum(len(x) - bisect_left(x, px) for x in xs[py:]) for px, py in points]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(\n",
    "        self, \n",
    "        rects: List[List[int]], \n",
    "        points: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        \n",
    "        h2l = defaultdict(SortedList)\n",
    "        for l, h in rects:\n",
    "            h2l[h].add(l)\n",
    "\n",
    "        res = [0] * len(points)\n",
    "\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            for h, ls in h2l.items():\n",
    "                if 0 <= y <= h:\n",
    "                    res[i] += len(ls) - ls.bisect_left(x)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # 按纵坐标排序\r\n",
    "    def countRectangles1(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\r\n",
    "        rectangles.sort(key=lambda r: -r[1])\r\n",
    "        n = len(points)\r\n",
    "        ans = [0] * n\r\n",
    "        i, xs = 0, []\r\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\r\n",
    "            start = i\r\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\r\n",
    "                xs.append(rectangles[i][0])\r\n",
    "                i += 1\r\n",
    "            if start < i:\r\n",
    "                xs.sort()  # 只有在 xs 插入了新元素时才排序\r\n",
    "            ans[id] = i - bisect_left(xs, x)\r\n",
    "        return ans\r\n",
    "        \r\n",
    "    # 如果纵坐标范围也是10^9\r\n",
    "    def countRectangles2(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\r\n",
    "        from sortedcontainers import SortedList\r\n",
    "        rectangles.sort(key=lambda r: -r[1])\r\n",
    "        n = len(points)\r\n",
    "        ans = [0] * n\r\n",
    "        i, xs = 0, SortedList()\r\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\r\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\r\n",
    "                xs.add(rectangles[i][0])\r\n",
    "                i += 1\r\n",
    "            ans[id] = i - xs.bisect_left(x)\r\n",
    "        return ans\r\n",
    "\r\n",
    "    # 按横坐标排序\r\n",
    "    def countRectangles3(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\r\n",
    "        rectangles.sort(key=lambda r: -r[0])\r\n",
    "        n = len(points)\r\n",
    "        ans = [0] * n\r\n",
    "        cnt = [0] * (max(y for _, y in rectangles) + 1)\r\n",
    "        i = 0\r\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][0]):\r\n",
    "            while i < len(rectangles) and rectangles[i][0] >= x:\r\n",
    "                cnt[rectangles[i][1]] += 1\r\n",
    "                i += 1\r\n",
    "            ans[id] = sum(cnt[y:])\r\n",
    "        return ans\r\n",
    "        \r\n",
    "    # 按行统计+二分\r\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\r\n",
    "        max_y = max(y for _, y in rectangles)\r\n",
    "        xs = [[] for _ in range(max_y + 1)]\r\n",
    "        for x, y in rectangles:\r\n",
    "            xs[y].append(x)\r\n",
    "        for x in xs:\r\n",
    "            x.sort()\r\n",
    "        return [sum(len(x) - bisect_left(x, px) for x in xs[py:]) for px, py in points]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles_list = [list() for _ in range(100)]\n",
    "        for rectangle in rectangles:\n",
    "            rectangles_list[rectangle[1] - 1].append(rectangle[0])\n",
    "        for height in rectangles_list:\n",
    "            height.sort()\n",
    "        ans = list()\n",
    "        for point in points:\n",
    "            cnt = 0\n",
    "            for i in range(point[1] - 1, 100):\n",
    "                cnt += len(rectangles_list[i]) - bisect_left(rectangles_list[i], point[0])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h = [[] for _ in range(101)]\n",
    "        for x, y in rectangles:\n",
    "            h[y].append(x)\n",
    "        for x in h:\n",
    "            x.sort()\n",
    "        ans = []\n",
    "        for x, y in points:\n",
    "            s = 0\n",
    "            for j in range(y, 101):\n",
    "                s += len(h[j]) - bisect_left(h[j], x)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        plen = len(points)\n",
    "        count = [0]*plen\n",
    "        n = len(rectangles)\n",
    "        rectangles.sort()\n",
    "\n",
    "        maxh = -1\n",
    "        for i in range(n):\n",
    "            maxh = max(maxh, rectangles[i][1])\n",
    "        rec = [[] for _ in range(maxh)]\n",
    "        for l,h in rectangles:\n",
    "            rec[h-1].append(l)\n",
    "\n",
    "        for i,(x,y) in enumerate(points):\n",
    "            cot = 0\n",
    "            for j in range(y-1, maxh):\n",
    "                cur_list = rec[j]\n",
    "                idx = bisect_left(cur_list, x)\n",
    "                cot += (len(cur_list) - idx)\n",
    "            count[i] = cot\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        # 因为h和y的范围较小，可以枚举。用rec记录每个高度的x坐标，并排序\n",
    "        # 要判断一个点 (x,y)，从 rec中h>=y的列表中二分查找大于等于x的数即可\n",
    "        plen = len(points)\n",
    "        count = [0]*plen\n",
    "        n = len(rectangles)\n",
    "        rectangles.sort()\n",
    "\n",
    "        maxh = -1\n",
    "        for i in range(n):\n",
    "            maxh = max(maxh, rectangles[i][1])\n",
    "        rec = [[] for _ in range(maxh)]\n",
    "        for l,h in rectangles:\n",
    "            rec[h-1].append(l)\n",
    "\n",
    "        for i,(x,y) in enumerate(points):\n",
    "            cot = 0\n",
    "            for j in range(y-1, maxh):\n",
    "                cur_list = rec[j]\n",
    "                idx = bisect_left(cur_list, x)\n",
    "                cot += (len(cur_list) - idx)\n",
    "            count[i] = cot\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        xaxis = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            xaxis[y].append(x)\n",
    "        for x in xaxis.values():\n",
    "            x.sort()\n",
    "        ans = [0] * len(points)\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            for h in range(y, 101):\n",
    "                if not xaxis[h] or xaxis[h][-1] < x: continue\n",
    "                n = len(xaxis[h])\n",
    "                l, r = 0, n - 1\n",
    "                while l < r:\n",
    "                    mid = l + r >> 1\n",
    "                    if xaxis[h][mid] >= x: r = mid\n",
    "                    else: l = mid + 1\n",
    "                #print(i, h, l, xaxis[h])\n",
    "                ans[i] += n - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\r\n",
    "        mp = [[] for _ in range(101)]\r\n",
    "        for l, h in rectangles:\r\n",
    "            mp[h] .append(l)\r\n",
    "        for i in range(101):\r\n",
    "            mp[i].sort()\r\n",
    "        res = []\r\n",
    "        for x, y in points:\r\n",
    "            cur = 0\r\n",
    "            for i in range(y, 101):\r\n",
    "                cur += len(mp[i]) - bisect_left(mp[i], x)\r\n",
    "            res.append(cur)\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        max_y = max(y for _, y in rectangles)\n",
    "        xs = [[] for _ in range(max_y + 1)]\n",
    "        for x, y in rectangles:\n",
    "            xs[y].append(x)\n",
    "\n",
    "        for x in xs:\n",
    "            x.sort()\n",
    "        list1=[]\n",
    "        for px,py in points:\n",
    "            list1.append(sum(len(x) - bisect_left(x, px) for x in xs[py:]))\n",
    "\n",
    "        return list1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        ys = [[] for _ in range(101)]\n",
    "        for x, y in rectangles:\n",
    "            ys[y].append(x)\n",
    "        for t in ys:\n",
    "            t.sort()\n",
    "        for x, y in points:\n",
    "            r = 0\n",
    "            for t in range(y, 101):\n",
    "                xs = ys[t]\n",
    "                L = len(xs)\n",
    "                ind = bisect.bisect_left(xs, x)\n",
    "                r += L - ind\n",
    "            res.append(r)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        1 <= rectangles.length, points.length <= 5 * 10^4\n",
    "        rectangles[i].length == points[j].length == 2\n",
    "        1 <= li, xj <= 10^9\n",
    "        1 <= hi, yj <= 100\n",
    "        \"\"\"\n",
    "        rectangles.sort()\n",
    "        rec = defaultdict(list)\n",
    "        for l, h in rectangles:\n",
    "            rec[h].append(l)\n",
    "        rec_ls = sorted(rec.keys())\n",
    "        ret = [0] * len(points)\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            yp = bisect.bisect_left(rec_ls, y)\n",
    "            for l in rec_ls[yp:]:\n",
    "                xp = bisect.bisect_left(rec[l], x)\n",
    "                ret[i] += len(rec[l]) - xp\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        dp=[[] for i in range(101)]\n",
    "        for x,y in rectangles:\n",
    "            dp[y].append(x)\n",
    "        for i in range(101):\n",
    "            dp[i].sort()\n",
    "        \n",
    "        res=[]\n",
    "        for x,y in points:\n",
    "            e=0\n",
    "            for i in range(y,101):\n",
    "                e+=len(dp[i]) -bisect_left(dp[i],x)\n",
    "            res.append(e)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            h[y].append(x)\n",
    "        for x in h.values():\n",
    "            x.sort()\n",
    "        ans = []\n",
    "        hh = sorted(h.keys())\n",
    "        print(f'hh:{hh}')\n",
    "        for x, y in points:\n",
    "            s = 0\n",
    "            y1 = bisect_left(hh, y)\n",
    "            print(f'y1:{y1},')\n",
    "            for j in range(y1, len(hh)):\n",
    "                k = hh[j]\n",
    "                s += len(h[k]) - bisect_left(h[k], x)\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        res = [0] * len(points)\n",
    "        # 计算高度大于每个纵坐标的所有矩形的长度，并以升序返回\n",
    "        @cache\n",
    "        def lengths(y: int):\n",
    "            res = []\n",
    "            for l, h in rectangles:\n",
    "                if h >= y:\n",
    "                    res.append(l)\n",
    "            return sorted(res)\n",
    "        \n",
    "        # 遍历所有纵坐标\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            llist = lengths(y)\n",
    "            res[i] = len(llist) - bisect_left(llist, x)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        m = len(points)\n",
    "        ans = [0]*m\n",
    "        n = len(rectangles)\n",
    "        rectangles.sort(key=lambda it: -it[0])\n",
    "        ind = list(range(m))\n",
    "        ind.sort(key=lambda it: -points[it][0])\n",
    "        i = 0\n",
    "        pre = SortedList()\n",
    "        for j in ind:\n",
    "            x, y = points[j]\n",
    "            while i < n and rectangles[i][0] >= x:\n",
    "                pre.add(rectangles[i][1])\n",
    "                i += 1\n",
    "            ans[j] = len(pre) - pre.bisect_left(y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, r: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        r.sort(reverse=True)\n",
    "        p = [(x, y, i) for i, (x, y) in enumerate(points)]\n",
    "        p.sort(reverse=True)\n",
    "    \n",
    "        nr = len(r)\n",
    "        np = len(p)\n",
    "        dp = [0] * 101\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = [0] * np\n",
    "        while j < np:\n",
    "            while i < nr and r[i][0] >= p[j][0]:\n",
    "                x, y = r[i]\n",
    "                for k in range(1, y + 1):\n",
    "                    dp[k] += 1\n",
    "                i += 1\n",
    "            px, py, pi = p[j]\n",
    "            ans[pi] = dp[py]\n",
    "            j += 1\n",
    "\n",
    "        return ans \n",
    "        \n",
    "            \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        def K(x):\n",
    "            return -x[0],x[1]\n",
    "        rectangles.sort(key = K)\n",
    "        for rec in rectangles:\n",
    "            dic[rec[1]].append(rec[0])\n",
    "        def db(x,arr):\n",
    "            l,r = 0, len(arr)-1\n",
    "            while l <= r:\n",
    "                mid = (l+r)//2\n",
    "                if arr[mid]>=x:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            #print(arr,x,l)\n",
    "            return l\n",
    "        ans = [0] * len(points)\n",
    "        for i in range(len(points)):\n",
    "            for j in range(points[i][1],101):\n",
    "                if len(dic[j]) == 0:\n",
    "                    continue\n",
    "                ans[i] += db(points[i][0],dic[j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        # 1 <= rectangles.length, points.length <= 5 * 104;;\n",
    "        # 这数据范围是不可能暴力了，显然是离线查询\n",
    "        rectangles.sort()\n",
    "        \n",
    "        points = [(x, y, i) for i, (x, y) in enumerate(points)]\n",
    "        points.sort(reverse=True)\n",
    "        \n",
    "        ans = [0] * len(points)\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList([])\n",
    "        \n",
    "        for x, y, i in points:\n",
    "            while rectangles and  rectangles[-1][0] >= x:\n",
    "                sl.add(rectangles.pop()[1])\n",
    "            v = len(sl) - sl.bisect_left(y)\n",
    "            ans[i] = v\n",
    "    \n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        res = [0] * len(points)\n",
    "        rectangles.sort(reverse=True)\n",
    "        a = [[p[0], p[1], i] for i, p in enumerate(points)]\n",
    "        a.sort(reverse=True)\n",
    "        n, k = len(rectangles), 0\n",
    "        count = [0] * 101\n",
    "        for x, y, i in a:\n",
    "            while k < n and rectangles[k][0] >= x:\n",
    "                for h in range(rectangles[k][1] + 1):\n",
    "                    count[h] += 1\n",
    "                k += 1\n",
    "            res[i] = count[y]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += v\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self, i):\n",
    "        # prefix sum\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        sortedR = sorted(rectangles, key=lambda x:-x[0])\n",
    "        sortedP = sorted(enumerate(points), key=lambda x:-x[1][0])\n",
    "        ans = [0] * len(points)\n",
    "\n",
    "        \"\"\"\n",
    "        mp = {}\n",
    "        for i, x in enumerate(sorted([y for _,y in rectangles] + [y for _,y in points]), start=1):\n",
    "            # 可能有重复值，所以i != len(mp) + 1\n",
    "            mp[x] = i\n",
    "        bit = Bit(i)\n",
    "\n",
    "        i = 0\n",
    "        for j,(x,y) in sortedP:\n",
    "            while i < len(sortedR) and sortedR[i][0] >= x:\n",
    "                bit.add(mp[sortedR[i][1]], 1)\n",
    "                i += 1 #目前有多少个矩形\n",
    "            ans[j] = i - bit.query(mp[y]-1) # 总数 - 高度小于y的矩形个数\n",
    "        \"\"\"\n",
    "        # 本题y值 <=100,不需要离散化\n",
    "        bit = Bit(100)\n",
    "        i = 0\n",
    "        for j,(x,y) in sortedP:\n",
    "            while i < len(sortedR) and sortedR[i][0] >= x:\n",
    "                bit.add(sortedR[i][1], 1)\n",
    "                i += 1 #目前有多少个矩形\n",
    "            ans[j] = i - bit.query(y-1) # 总数 - 高度小于y的矩形个数\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n\n",
    "        i, xs = 0, []\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            start = i\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            if start < i:\n",
    "                xs.sort()  # 只有在 xs 插入了新元素时才排序\n",
    "            ans[id] = i - bisect_left(xs, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n\n",
    "        i, xs = 0, []\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            start = i\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            if start < i:\n",
    "                xs.sort()  # 只有在 xs 插入了新元素时才排序\n",
    "            ans[id] = i - bisect_left(xs, x)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n\n",
    "        i, xs = 0, []\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            start = i\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            if start < i:\n",
    "                xs.sort()  # 只有在 xs 插入了新元素时才排序\n",
    "            ans[id] = i - bisect_left(xs, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda x: -x[0])\n",
    "        n = len(points)\n",
    "        m = len(rectangles)\n",
    "        ans = [0] * n\n",
    "        c = Counter()\n",
    "        idx = 0\n",
    "        for i, (x, y) in sorted(zip(range(n), points), key=lambda x: -x[1][0]):\n",
    "            # 横坐标大于等于该点的矩形才可能满足要求\n",
    "            while idx < m and x <= rectangles[idx][0]:\n",
    "                c[rectangles[idx][1]] += 1\n",
    "                idx += 1\n",
    "            ans[i] = sum(v for k, v in c.items() if k >= y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda x: -x[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n\n",
    "        i = 0\n",
    "        st = SortedList()\n",
    "        for idx, (x, y) in sorted(zip(range(n), points), key=lambda x: -x[1][1]):\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                st.add(rectangles[i][0])\n",
    "                i += 1\n",
    "            ind = st.bisect_left(x)\n",
    "            ans[idx] = len(st) - ind\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key = lambda x : -x[1])\n",
    "        n = len(points)\n",
    "        i, xs = 0, []\n",
    "        ans = [0] * n\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key = lambda x : -x[0][1]):\n",
    "            start = i\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            if start < i:\n",
    "                xs.sort()\n",
    "            ans[id] = i - bisect.bisect_left(xs, x)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n \n",
    "        i, xs = 0, []\n",
    "        # 使用zip记住原来的次序\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            start = i \n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            if start < i:\n",
    "                xs.sort()\n",
    "            ans[id] = i - bisect_left(xs, x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        # 将矩形按高度进行降序排序\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        \n",
    "        n = len(points)\n",
    "        ans = [0] * n  # 结果数组\n",
    "        \n",
    "        i, xs = 0, []  # i 用于遍历 rectangles，xs 用于存储当前所有矩形的宽度\n",
    "        \n",
    "        # 按 y 坐标对点进行降序排序，同时保留点的原始索引\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            start = i\n",
    "            \n",
    "            # 从当前点开始，找到所有比这个点更高的矩形\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.append(rectangles[i][0])\n",
    "                i += 1\n",
    "            \n",
    "            # 只有在 xs 插入了新元素时才进行排序\n",
    "            if start < i:\n",
    "                xs.sort()\n",
    "            \n",
    "            # 使用二分搜索找到比 x 小的最大矩形宽度的数量\n",
    "            ans[id] = i - bisect_left(xs, x)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        rectangles.sort(key=lambda r: -r[1])\n",
    "        n = len(points)\n",
    "        ans = [0] * n \n",
    "        i, xs = 0, SortedList()\n",
    "        # 使用zip记住原来的次序, 询问也从大到小询问\n",
    "        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):\n",
    "            while i < len(rectangles) and rectangles[i][1] >= y:\n",
    "                xs.add(rectangles[i][0])\n",
    "                i += 1\n",
    "            ans[id] = i - xs.bisect_left(x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# bisect_left(x)是大于等于x的第一个下标\n",
    "# bisect_right(x)是大于x的第一个下标\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        def cnt_h(y):\n",
    "            # 统计纵坐标大于等于y的矩阵的横坐标\n",
    "            # m是rectangles长度\n",
    "            # 时间复杂度 O(m+log(m))\n",
    "            res = []\n",
    "            for l,h in rectangles:\n",
    "                if h >= y:\n",
    "                    res.append(l)\n",
    "            res.sort()\n",
    "            return res\n",
    "        # 将需要查询的纵坐标相同的放在一起，这样就不需要每次都去统计横坐标矩阵了\n",
    "        p = defaultdict(list)\n",
    "        n = len(points)\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            p[points[i][1]].append((points[i][0],i))\n",
    "        # 开始查询\n",
    "        for h,plist in p.items():\n",
    "            xlist = cnt_h(h)\n",
    "            for x,i in plist:\n",
    "                ans[i] = len(xlist)-bisect_left(xlist,x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        res = [0] * n   # 记录结果\n",
    "        p = defaultdict(list)   # 记录每个纵坐标对应点的横坐标与下标\n",
    "        for i in range(n):\n",
    "            p[points[i][1]].append((points[i][0], i))\n",
    "        # 计算高度大于每个纵坐标的所有矩形的长度，并以升序返回\n",
    "        def lengths(y: int):\n",
    "            res = []\n",
    "            for l, h in rectangles:\n",
    "                if h >= y:\n",
    "                    res.append(l)\n",
    "            return sorted(res)\n",
    "        \n",
    "        # 遍历所有纵坐标\n",
    "        for h, plist in p.items():\n",
    "            llist = lengths(h)\n",
    "            for x, idx in plist:\n",
    "                # 二分查找计算覆盖矩形数量并更新结果数组\n",
    "                res[idx] = len(llist) - bisect.bisect_left(llist, x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        n = len(points)\n",
    "        res = [0] * n   # 记录结果\n",
    "        p = defaultdict(list)   # 记录每个纵坐标对应点的横坐标与下标\n",
    "        for i in range(n):\n",
    "            p[points[i][1]].append((points[i][0], i))\n",
    "        # 计算高度大于每个纵坐标的所有矩形的长度，并以升序返回\n",
    "        def lengths(y: int):\n",
    "            res = []\n",
    "            for l, h in rectangles:\n",
    "                if h >= y:\n",
    "                    res.append(l)\n",
    "            return sorted(res)\n",
    "        \n",
    "        # 遍历所有纵坐标\n",
    "        for h, plist in p.items():\n",
    "            llist = lengths(h)\n",
    "            for x, idx in plist:\n",
    "                # 二分查找计算覆盖矩形数量并更新结果数组\n",
    "                res[idx] = len(llist) - bisect.bisect_left(llist, x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# bisect_left(x)是大于等于x的第一个下标\n",
    "# bisect_right(x)是大于x的第一个下标\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        # 调用一次的时间复杂度为O(mlogm)\n",
    "        def lengths(y):\n",
    "            res = []\n",
    "            for l,h in rectangles:\n",
    "                if h >= y:\n",
    "                    res.append(l)\n",
    "            return sorted(res)\n",
    "        n = len(points)\n",
    "        ans = [0]*n\n",
    "        p = defaultdict(list)\n",
    "        # 纵坐标:(横坐标，下标)\n",
    "        for i in range(n):\n",
    "            p[points[i][1]].append((points[i][0],i))\n",
    "\n",
    "        for h,plist in p.items():\n",
    "            llist = lengths(h)\n",
    "            for x,index in plist:\n",
    "                ans[index] = len(llist)-bisect_left(llist,x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        array = SortedList()\n",
    "        # array.add(- float('inf'))\n",
    "        # array.add(float('inf'))\n",
    "        rectangles.sort(key = lambda x: x[0])\n",
    "        res = [0] * len(points)\n",
    "        pt = sorted([(idx, p[0], p[1]) for idx, p in enumerate(points)], key = lambda x: - x[1])\n",
    "        for idx, x, y in pt:\n",
    "            while rectangles and rectangles[-1][0] >= x:\n",
    "                a, b = rectangles.pop()\n",
    "                array.add(b)\n",
    "            if not array:\n",
    "                continue \n",
    "            i = bisect_left(array, y)\n",
    "            if i < len(array):\n",
    "                res[idx] = len(array) - i\n",
    "        return res \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "\n",
    "        rectangles.sort()\n",
    "        d = defaultdict(list)\n",
    "        for x, y in rectangles:\n",
    "            d[y].append(x)\n",
    "\n",
    "        n = len(points)\n",
    "        ans = [0] * n\n",
    "        ys = sorted(d.keys(), reverse=True)\n",
    "        i = 0\n",
    "        st = SortedList()\n",
    "        for idx, (x, y) in sorted(zip(range(n), points), key=lambda x: -x[1][1]):\n",
    "            while i < len(ys) and ys[i] >= y:\n",
    "                for l in d[ys[i]]:\n",
    "                    st.add(l)\n",
    "                i += 1\n",
    "            ind = st.bisect_left(x)\n",
    "            ans[idx] = len(st) - ind\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += v\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self, i):\n",
    "        # prefix sum\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        sortedR = sorted(rectangles, key=lambda x:-x[0])\n",
    "        sortedP = sorted(enumerate(points), key=lambda x:-x[1][0])\n",
    "        ans = [0] * len(points)\n",
    "\n",
    "        #mp = { x: i for i, x in enumerate(sorted([y for _,y in rectangles] + [y for _,y in points]), start=1) }\n",
    "        mp = {}\n",
    "        for i, x in enumerate(sorted([y for _,y in rectangles] + [y for _,y in points]), start=1):\n",
    "            # 可能有重复值，所以i != len(mp) + 1\n",
    "            mp[x] = i\n",
    "        bit = Bit(i)\n",
    "\n",
    "        i = 0\n",
    "        for j,(x,y) in sortedP:\n",
    "            while i < len(sortedR) and sortedR[i][0] >= x:\n",
    "                bit.add(mp[sortedR[i][1]], 1)\n",
    "                i += 1 #目前有多少个矩形\n",
    "            ans[j] = i - bit.query(mp[y]-1) # 总数 - 高度小于y的矩形个数\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT1:\n",
    "    \"\"\"单点修改,区间和查询\"\"\"\n",
    "\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.bit = n.bit_length()\n",
    "        self.tree = [0]*(n+1)\n",
    "\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index]+=delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int: \n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "class Solution:\n",
    "    def countRectangles(self, arr: List[List[int]], brr: List[List[int]]) -> List[int]:\n",
    "        d=[]\n",
    "        for i,j in arr:\n",
    "            d+=[i,j]\n",
    "        for i,j in brr:\n",
    "            d+=[i,j]\n",
    "        d=sorted(set(d))\n",
    "        d={a:i+1 for i,a in enumerate(d)}\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        n=len(brr)\n",
    "        res=[0]*n\n",
    "        bit=BIT1(len(d)+10)\n",
    "        brr=[[i]+brr[i] for i in range(n)]\n",
    "        brr.sort(key=lambda x:-x[1])\n",
    "        for i,x,y in brr:\n",
    "            while arr and arr[-1][0]>=x:\n",
    "                a,b=arr.pop()\n",
    "                bit.add(d[b],1)\n",
    "            res[i]=bit.query(d[y],len(d)+5)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def binarySearch(ls, length, k):\n",
    "    if len(ls) == 0: \n",
    "        return 0\n",
    "    if ls[0] >= k:\n",
    "        return length\n",
    "    elif ls[-1] < k:\n",
    "        return 0\n",
    "    elif ls[-1] >= k and ls[0] < k:\n",
    "        len_div_2 = int(length / 2)\n",
    "        return binarySearch(ls[:len_div_2], len_div_2, k) + \\\n",
    "        binarySearch(ls[len_div_2:], length - len_div_2, k) \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h_dict = {i: [] for i in range(1, 101)}\n",
    "        for rectangle in rectangles:\n",
    "            l, h = rectangle\n",
    "            h_dict[h].append(l)\n",
    "        \n",
    "        h_dict[100].sort()\n",
    "        for h1 in range(99, 0, -1):\n",
    "            h_dict[h1] = h_dict[h1 + 1] + h_dict[h1]\n",
    "            h_dict[h1].sort()\n",
    "        \n",
    "        counts = [0 for _ in points]\n",
    "        for idx, point in enumerate(points):\n",
    "            x, y = point\n",
    "            # ls = []\n",
    "            # for h in range(y, 101):\n",
    "            ls = h_dict[y]\n",
    "            counts[idx] = binarySearch(ls, len(ls), x)\n",
    "        \n",
    "        return counts\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def binarySearch(ls, length, k):\n",
    "    if len(ls) == 0: \n",
    "        return 0\n",
    "    if ls[0] >= k:\n",
    "        return length\n",
    "    elif ls[-1] < k:\n",
    "        return 0\n",
    "    elif ls[-1] >= k and ls[0] < k:\n",
    "        len_div_2 = int(length / 2)\n",
    "        return binarySearch(ls[:len_div_2], len_div_2, k) + \\\n",
    "        binarySearch(ls[len_div_2:], length - len_div_2, k) \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:\n",
    "        h_dict = {i: [] for i in range(1, 101)}\n",
    "        for rectangle in rectangles:\n",
    "            l, h = rectangle\n",
    "            h_dict[h].append(l)\n",
    "        \n",
    "        h_dict[100].sort()\n",
    "        for h1 in range(99, 0, -1):\n",
    "            h_dict[h1] = h_dict[h1 + 1] + h_dict[h1]\n",
    "            h_dict[h1].sort()\n",
    "        \n",
    "        counts = [0 for _ in points]\n",
    "        for idx, point in enumerate(points):\n",
    "            x, y = point\n",
    "            ls = []\n",
    "            # for h in range(y, 101):\n",
    "            ls = h_dict[y]\n",
    "            counts[idx] += binarySearch(ls, len(ls), x)\n",
    "        \n",
    "        return counts\n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
